import java.util.Arrays;

public class MyStack {
    public int[] elem;
    public int usedSize;

    public MyStack() {
        this.elem = new int[5];//初始化数组空间
    }
    public void push(int data){
        //判断栈是否满了
        if(isFull()){
             elem = Arrays.copyOf(elem,elem.length*2);
        }
       elem[usedSize] = data;
        usedSize++;
    }

    public boolean isFull(){
        return usedSize == elem.length;
    }
    public int pop(){
        //判断栈不为空
        if(empty()){
            //抛出异常
            throw new StackEmptyException("栈为空！！");
        }
        //开始删除
        return elem[--usedSize];
    }

    public boolean empty(){
        return usedSize == 0;
    }
    public int peek(){
        //判断栈不为空
        if(empty()){
            //抛出异常
            throw new StackEmptyException("栈为空！！");
        }
        return elem[usedSize-1];
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 如果两个链表有一个为空，则一定不会相交
        if(null == headA || null == headB){
            return null;
        }
        // 找到两个链表的最后一个节点，找的过程中统计链表的长度
        ListNode curA = headA;
        int sizeA = 1;  // 从1开始是因为cur在最后一个节点时循环进不去
        while(null != curA.next){
            curA = curA.next;
            ++sizeA;
        }
        ListNode curB = headB;
        int sizeB = 1;
        while(null != curB.next){
            curB = curB.next;
            sizeB++;
        }
        // 如果两个链表最后一个节点不同，则一定不相交，否则相交
        if(curA != curB){
            return null;
        }
        // 让长的链表从头先走两个链表差值步，然后两个引用同时往后走
        curA = headA;
        curB = headB;
        int gap = sizeA - sizeB;
        if(gap > 0){
            // curA长
            while(0 != gap){
                curA = curA.next;
                --gap;
            }
        }else{
            // curB长
            while(0 != gap){
                curB = curB.next;
                ++gap;
            }
        }
        // curA和curB同时往后移动，相遇的时候即为交点
        while(curA != curB){
            curA = curA.next;
            curB = curB.next;
        }
        return curA;
    }

    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(null != fast && null != fast.next){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }

    public ListNode detectCycle(ListNode head) {
        // 1. 先检测是否相交
        ListNode fast = head;
        ListNode slow = head;
        boolean isCross = false;
        while(null != fast && null != fast.next){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                isCross = true;
                break;
            }
        }
        // 如果不相交，则没有交点
        if(!isCross){
            return null;
        }
        // 相交：求交点
        // 让一个引用从链表起始位置移动，一个从相遇点位置移动，两个引用都每次只走一步
        // 相遇时则为交点
        ListNode pH = head;
        ListNode pM = fast;
        while(pH != pM){
            pH = pH.next;
            pM = pM.next;
        }
        return pH;
    }
}
